模拟赛题解/2025.8.24 模拟赛

T1-字符串(string)

题面

给定一个长为 $n$ 的仅由小写字母组成的字符串 $s$。

可以选择两个正整数 $l,r$ 满足 $1\leq l\leq r\leq n$，对 $[s_l,s_r]$ 的区间进行翻转。

求通过一次翻转，最多能得到多少种不同的字符串。

$1\leq n\leq2\times10^5$。

题解

注意到，对于所有首尾字符相同的子串，它的反转操作都能等效为去掉其首尾字符的新子串的反转操作。

所以我们只需要统计有多少个点对互不相同即可。

T2-子序列(subsequence)

题面

给定一个长度为 $n$ 的整数序列 $a$，对其每个子序列求和可以得到 $2^n$ 个数，求其中前 $k$ 小的数。

$1\leq n\leq2\times10^5，1\leq k\leq\min(2^n,10^6),-10^9\leq a_i\leq10^9$。

题解

如果 $a$ 非负，可以观察到我们每次增加只会是增加一个数或者替换一个数，我们用一个优先队列存储，可以 $O(n\log n)$ 解决。

考虑有负数的情况， 设负数是 $-x$，我们直接将 $-x$ 换为 $x$ ，选/不选的情况就会从 $0/-x$ 变成 $x/0$，注意到我们只需要将所有答案减少 $x$，此时的情况就与原本一致，按照全是正数计算即可。

T3-划分(divide)

题面

有一个 $n\times n$ 的网格，第 $i$ 行第 $j$ 列的格子记作 $(i,j)$。

定义一个级别 $k$ 的 $L$ 型为两边长（包括拐点）均为 $k$ 的 $L$ 型，可以旋转，特殊地，级别 $1$ 的 $L$ 型仅包含一个方格。

给定格子 $(x,y)$，考虑将整个网格划分为级别 $1,\cdots,n$ 的 $L$ 型各一个的所有方法（划分时每个格子属于且仅属于一个 $L$ 型），求 $(x,y)$ 属于的 $L$ 型的级别之和，结果对 $10^9+7$​ 取模后输出。

$1\leq n\leq10^7,1\leq x,y\leq n$。

题解

最简单的写法是计算有多少种方法能使 $(x,y)$ 被分在 $\leq k$ 级别的 $L$ 型里，设为 $dp[k]$。

从大往小看，可以认为每次操作会使矩形上下缩一行，左右缩一列（或者可以认为矩形左上角最多往下移一行，最多往右移一列，矩形大小减 $1$）。

如果要把这个格子分到 $\leq k$ 级别的矩形里，那么前 $n-k$ 次缩矩形就不能把这个点缩没，分行列考虑，删掉最上方行的次数必须在 $[x-k,x-1]$ 范围内，同理删掉最左边列的次数必须在 $[y-k,y-1]$ 范围内，后边操作就是任意的了。

因此方案数就是 $\left(\sum_{i=x-k}^{x-1}C_{n-k}^i\right)\times\left(\sum_{i=y-k}^{y-1}C_{n-k}^i\right)\times 4^{n-1}$。

$k=n$ 时，两个括号内都是 $1$，式子结果是 $4^{n-1}$。

随着 $k$ 的减小 $n-k$ 增大，且 $C$ 的项数会少，这可以利用杨辉三角观察一下这一段和的规律，先乘 $2$ 推到下一行的一段区间 （会带点零碎的边界），再简单加减几项调整一下（减掉多余的贡献，如果缺项就加上缺少的项），这样可以做到 $O(1)$ 递推。

本题中应该是乘 $2$ 后原来那行最左最右的两项的贡献会算多一倍，所以应该就是减原来那行首尾两项，不用加。

最后答案可以用 $dp[n]\times n$（也就是 $4^{n-1}\times n$ ）减去前边每一项，相当于初始认为每一种方案级别都是 $n$，然后减去级别 $\leq n-1$ 的方案（这些方案的级别都损失了 $1$），然后减去级别 $\leq n-2$ 的方案（这些方案的级别又损失了 $1$），以此类推。

也可以用 $dp[n]-dp[n-1]$ 算出级别恰好为 $k$ 的方案数。

甚至可以直接分这个点出现在级别恰好为 $k$ 的 $L$ 型的角还是边上直接列出组合数前缀和形式的式子计算，但写法不如计算 $\leq k$ 的简便。

时间复杂度 $O(n)$。

T4-逆序对期望(reverse)

题面

现在你有一个 $n$ 个数的排列 $A[1\cdots n]$，你可以对它做两种操作：

1. 交换两个相邻元素；
2. 将整个排列随机打乱，随机打乱后出现任意一种排列的概率都是相等的 (即都是 $\frac{1}{n!}$)。

现在你最多对这个排列执行 $k$ 次操作（可以少于 $k$ 次）。整个过程中，你可以根据当前的排列情况，实时决策下一步是否停止操作，以及使用 1/2 哪种操作。

请问最优策略下，最终排列的逆序对数期望的最小可能值。

$1\leq t\leq10000,1\leq n\leq300,1\leq k\leq\binom{n}{2},tp=0,1,2$

题解

记 $rev$ 为输入排列 $A$ 中逆序对数量。

只有第 $1$ 种操作时，由于交换相邻元素只能让逆序对数 $-1$，答案为 $max(0,rev-K)$。

只有第 $2$ 种操作时，随机打乱后的逆序对数期望是一个定值，可以通过 DP 求出。设计 $f_{i,j}$ 代表 $1\cdots i$ 这些数随机打乱之后恰好有 $j$ 个逆序对的概率，转移为 $\displaystyle f_{i,j}=\frac{\sum_{k=0}^{i-1}f_{i-1,j-k}}{i}$。

利用前缀和优化可以在 $O(n^3)$ 时间完成。

令 $g_{i,j}$ 代表长度为 $i$ 的随机排列，进行 $j$ 次打乱之后的逆序对期望。

那么每次打乱之后都可以进行决策，停下来或者继续打乱（期望为 $g_{i,j-1}$），设当前逆序对数为 $t$，若 $t<g_{i,j-1}$ 则停下来，否则继续打乱。

设 $k=int(g_{i,j-1}):$

$$g_{i,j}=\sum_{t=0}^kt\times f_{i,t}+g_{i,j-1}\times\sum f_{i,k+1\cdots\binom{i}{2}}$$

答案为 $ans=min(rev,g_{n,K-1})$。

两种操作都有时，需要进行决策是否先使用操作 $2$ 进行打乱，令 $ans_{i,j}$ 代表长度为 $i$ 的随机排列，进行 $j$ 次最优操作之后的逆序对期 望，设当前逆序对数为 $t$，转移有2种：

• 使用 $j$ 次 $1$ 操作，得到的逆序对数量为 先打乱，得到的逆序对数量为 $t-j$
• 先打乱，得到的逆序对数为 $ans_{i,j-1}$

两种择优转移：若 $t\leq j+ans_{i,j-1}$ 使用第1种转移，否则第2种转移。设 $k=int(j+ans_{i,j-1})$。

$$ans_{i,j}=0\times\sum f_{i,0\cdots j}+2\times\sum f_{i,j+2}+\cdots+(k-j)\times\sum f_{i,k}+ans_{i,j-1}\times\sum f_{i,k+1\cdots\binom{i}{2}}$$

维护 $f_{i,j}$ 和 $j*f_{i,j}$ 的前缀和 s1_{i,j}$$s2_{i,j}，上式可以写成

$$ans_{i,j}=(s2_{i,k}-s2_{i,j})-j\times(s1_{i,k}-s1_{i,j})+ans_{i,j-1}\times(s1_{i,\binom{i}{2}}-s1_{i,k})$$

可以在 $O(n^3)$ 时间内预处理出 $ans$ 数组，答案为 $min(rev-K,ans_{n,K-1})$，总复杂度 $O(n^3+tn\log n)$。

注意空间较大，可以将 $f$ 数组滚动。